package ua.mykola.prime;

import java.util.BitSet;
import java.util.LinkedList;
import java.util.Queue;

public class SieveOfEratosthenes {
	public Queue<Integer> getPrimes(int ceiling) {
		BitSet bitSet = getPrimesBitSet(ceiling);
		return convertToIntegers(bitSet, ceiling);
	}

	private Queue<Integer> convertToIntegers(BitSet bitSet, int limit) {
		Queue<Integer> primes = new LinkedList<Integer>();
		for (int i = 2; i < limit; i++) {
			if (bitSet.get(i)) {
				primes.add(i);
			}
		}
		return primes;
	}

	private BitSet getPrimesBitSet(int limit) {
		BitSet bitSet = new BitSet(limit);
		bitSet.set(2, limit);
		for (int i = 2; i < limit; i++) {
			if (bitSet.get(i)) {
				for (int j = i * i; j < limit; j += i) {
					bitSet.clear(j);
				}
			}
		}
		return bitSet;
	}
}
